This invention relates to computer networks and, more specifically, to a method and apparatus for efficiently calculating checksums to detect data transmission errors.
In computer network systems, data is often encapsulated into data messages and transmitted among various entities of the system. A sending entity, for example, may formulate one or more data messages and transmit them across the network for receipt by a receiving entity. The receiving entity captures the data messages and retrieves the data. During transmission, however, errors can be introduced into the data. Accordingly, error control has become an integral part of computer network systems. One of the primary methods to control data transmission errors is known as error detection. With error detection, a receiving entity examines captured data messages to determine whether an error exists. If so, the receiving entity typically discards the data and requests its retransmission.
One of the more well-known error detection techniques is to calculate and append a checksum valve to each data message. Typically, an agreed-upon algorithm (e.g., a parity check, cyclic redundancy check, hashing function, summation of the number of bits in the packet equal to 1, summation of the numerical values represented by the data, etc.) is applied to the contents of the message prior to its transmission so as to generate a corresponding checksum. The generated checksum is then appended to the data message by the sending entity and the message is transmitted across the network. Upon receipt of the message, the receiving entity applies the same, agreed-upon algorithm to the contents of the message and determines whether its calculation of the checksum matches the checksum contained in the message. If so, the receiving entity concludes that no errors were introduced into the message during its transmission and, therefore, continues processing the data. If the two values do not match, the receiving entity assumes that errors are present in the data and the message is typically discarded.
FIG. 1 is a block diagram of a conventional network data message 100. Message 100, which corresponds to the well-known Transmission Control Protocol (TCP), includes a plurality of fields, including a source port field 102, a destination port field 104, a sequence number (SEQ. NO.) field 106, an acknowledgment number (ACK. NO.) field 108, a header length field 110, a window size field 112, a 16-bit checksum field 114, a pointer (PTR.) field 116, an options field 118 and a variable length data field 120 containing the contents of the message being transmitted. To calculate the checksum value pursuant to the TCP protocol, the checksum field 114 is initially set to zero and the data field 120 is padded with an additional zero byte if its length is an odd number. Next, the sending entity adds up all of the 16-bit portions of the message 100 in 1""s complement and then the 1""s complement of the sum is taken. In other words, all of the 16-bit portions of the message 100 are summed and the carry over values are added back into the sum. The 16-bit result is loaded into the checksum field 114 and the message 100 is transmitted across the network.
Checksum calculations can either be performed in software by the sending entity""s central processor unit (CPU) or in a hardware circuit designed to calculate checksums. Several hardware circuits are known for calculating checksums. In a first checksum generation circuit, two 16-bit registers are used with an adder circuit. In operation, the first register is zeroed and the first 16-bit word of the message 100 is fetched into the second register. The two registers are then added together and result placed in the first register. The carry bit resulting from the add operation is then added into the first register and the circuit is ready for the next 16-bit word of the message 100, which is processed in the same manner. After the last 16-bit word has been processed and the carry bit added back to the first register, the first register will contain the checksum value for loading into the checksum field 114.
In another known checksum generation circuit, two 32-bit registers and a corresponding adder circuit are used. Here, the first register is zeroed and the first 32-bits of the message 100 are fetched into the second register. The two registers are then added together and the result placed in the first register. The carry bit resulting from the add operation is then added into the first register and the circuit is ready for the next 32-bit segment of the message 100, which is processed in the same manner. After the last 32-bit segment of the message 100 has been processed and the carry bit added to the first register, the low order 16 bits of the register are added to the high order 16 bits and the result loaded into the low order 16 bits of the first register. The carry bit from this last addition is then added back to the low order 16 bits, which represent the final checksum.
U.S. Pat. No. 5,663,952 entitled CHECKSUM GENERATION CIRCUIT AND METHOD to Gentry, Jr., is directed to a checksum generation circuit using two 16-bit adder circuits to generate checksums on a 32-bit data stream. Here, the data stream is split into two 16-bit words and each adder circuit processes a respective 16-bit segment. Each adder circuit also adds back the carry bit for each add cycle and stores the result in a corresponding 16-bit register. After the last 32-bit segment has been processed, three additional steps are performed to obtain the final 16-bit checksum value. First, the 16-bit results produced by each adder circuit are added together along with the last remaining carry bit from the first adder circuit. Second, the last remaining carry bit from the second adder circuit is added back. Third, any carry bit resulting from the second step is added back in, thereby generating the checksum value. The final 16-bit checksum may then be loaded into the respective message.
By operating on two 16-bit words in parallel, the checksum generator of the ""952 patent purportedly speeds up the calculation of checksums. It nonetheless has several disadvantages. First, each addition step creates a resulting carry bit. This carry bit, moreover, must be added back in with the next addition step. Furthermore, the creation of any carry bit during the final processing must also be added back in to the final sum. Since most processors typically handle additions sequentially, the adding back of each carry bit requires an additional step consuming processor resources and time. Accordingly, a need has arisen to develop a checksum generator which can operate more efficiently.
Briefly, the present invention is directed to a method and apparatus for generating a checksum that minimizes the creation and manipulation of carry bits by allowing a xe2x80x9crunning sumxe2x80x9d to expand into a register having a larger capacity than the size of the message segments being processed. In particular, a checksum generator includes at least one adding circuit for processing a given message in segments. Associated with the adding circuit is a register for temporarily holding the running sum that is being calculated by the adding circuit. According to the invention, the register is configured to hold a running sum that is larger than the message segments being added by the adding circuit. Preferably, the register is twice the size of the message segments being processed and is segregated into a high order portion and a low order portion. For example, the adding circuit may be configured to process 16-bit message words and the register may be configured to store a 32-bit running sum and segregated into a high order 16-bit portion and a low order 16-bit portion. By coupling the adding circuit to a register that is larger than the corresponding message segments, the adding circuit can allow the running sum to expand into the register, thereby eliminating the creation of a carry bit that must be added back during each add cycle. After the last message segment has been processed, the adding circuit preferably adds the high order portion of the register to the low order portion and places the result in the low order portion, creating a carry bit. The adding circuit adds back the carry bit to the low order portion, thereby generating a checksum that may be loaded into the message.
In a further aspect of the invention, the checksum generator includes two adding circuits operating in parallel. The two adding circuits are coupled to a register, which is apportioned into two sections, such that the output of each adding circuit may be loaded into a respective section of the register. At least one of the register sections is further apportioned into a low order portion and a high order portion. The adding circuits, moreover, are configured to add a received message segment to the contents of their respective register sections and to store the result in their register sections. Each section of the register is larger than the message segments being processed by the adding circuits. Accordingly, each register section is able to hold a running sum without creating a carry bit that must be separately processed by the respective adding circuit. After the entire message has been processed, one of the adding circuits adds the contents of the two register sections together and places the result in a first section of the register, creating a first carry bit. The first carry bit is added back to the contents of the first register section and the new result loaded into the first register section. Next, the adding circuit adds the low order portion to the high order portion of the first register section, creating a second carry bit. The second carry bit is added back to the contents of the low order portion of the first register section, thereby generating a checksum that may be loaded into the respective message.